package com.sicheng.lc.周赛.分类.排列组合计数;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/24 22:08
 */
public class 选择建筑的方案数 {
    //https://leetcode.cn/problems/number-of-ways-to-select-buildings/
    public long numberOfWays(String s) {
        //大致思路
        // 只能选择010 , 101这种类型
        // 统计 0  ,和 1 的总个数 total0, s.length()-total0
        // 当当前是1时 前面出现了 c0 个 0     后面还有 total0-c0 个0
        // 当当前是0时 前面出现了 i+1-c0 个1  后面还有 s.length() - total0 - (i + 1 - c0)个1
        int total0 = 0;
        int c0 = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0')
                total0++;
        }
        long res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                res += (long) c0 * (total0 - c0);
            } else {
                c0++;
                res += (long) (i + 1 - c0) * (s.length() - total0 - (i + 1 - c0));
            }
        }
        return res;
    }
}
